package algorithm;

import java.util.*;

/**
 * @author MaGuangQi
 * @description
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
 * @date 2020-06-08 22:49
 **/
public class TwoSum {
    //解法1.暴力解法
    public static int[] twoSum(int[] nums, int target) {

        //排序(不正确,数据量大会导致复杂度变高o(n^2))
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length - 1; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0]=i;
                    result[1]=j;
                    return result;
                }else if (nums[i] + nums[j] > target){
                    //直接break,因为后面的数肯定比他们还大
                    break;
                }
            }
        }
        return result;
    }

    //解法二.利用hash表解决
    //hash表key 为元素,value为索引值,利用target去减hash表元素,如果hash表包含,说明是,返回元素index
    //例如 第一个是2,9-2=7,在hash表找7,没有,继续放,然后9-11=-2,找-2,以此类推
    //时间复杂度：O(n)
    //nums = [2, 11, 7, 15], target = 9
    //我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间
    public static int[] twoSum2(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> elementMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {

            int tmpValue = target - nums[i];
            //包含说明是,恰好key是tmpValue,value是index
            if (elementMap.containsKey(tmpValue)) {
//                result[0]=elementMap.get(nums[i]);
//                result[1]=elementMap.get(tmpValue);
                //优化, i其实就是index
                return new int[]{elementMap.get(tmpValue), i};
            }
            //注意顺序,应该是先减,不成功再放入map
            elementMap.put(nums[i],i);
        }
        return result;
    }

    public static void main(String[] args) {
      int[]  nums =new int[] {3,2,4};
        //int[] ints = twoSum(nums,18);
        int[] ints = twoSum2(nums,6);
        System.out.println("第一个"+ints[0]+"第二个"+ints[1]);
    }
}
